/**
 * 词典中最长的单词
 *
 * 给出一个字符串数组 words 组成的一本英语词典。返回能够通过 words 中其它单词逐步添加一个字母来构造得到的 words 中最长的单词。
 * 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
 * 请注意，单词应该从左到右构建，每个额外的字符都添加到前一个单词的结尾。
 *
 * 示例 1：
 * 输入：words = ["w","wo","wor","worl", "world"]
 * 输出："world"
 * 解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。
 *
 * 示例 2：
 * 输入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
 * 输出："apple"
 * 解释："apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply"
 */

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 我们先用 set 存储所以已经出现的字符串, 因为题目要求在长度相同时返回字典序
 * 在前面的, 所以我们先将数组按照字典序排序, 然后再判断, 如何判断呢? 我们一个一个
 * 判断吧, 将每个字符一点一点从后向前切割, 要是全都在 set 中存在, 就说明这个是都存在的
 * 可以判断长度... 这里我们可以进行一下优化, 就是先判断长度, 要是不达标, 就直接
 * 跳过了...
 * 时间复杂度 : O(n * max(log(n), words.maxLength)
 * 空间复杂度 : O(n)
 */

public class Main {
    public String longestWord(String[] words) {

        // 存储出现的字符串
        Set<String> hash = new HashSet<>();

        // 存储
        for (String s : words) {
            hash.add(s);
        }

        // 排序, 因为题目有要求长度相同需要按照字典序排序, 所以我们先将
        // 数组按照字典序排序好
        Arrays.sort(words);

        // 最长长度
        int max = 0;

        // 最终返回的结果
        String res = "";

        // 遍历数组
        for (String s : words) {

            int n = s.length();

            // 长度只有大于才需要更新, 等于不用判断了, 因为已经按照字典序排序了
            if (n > max) {

                // 是否都存在的标志
                boolean tmp = true;

                // 判断是否都存在
                while (n > 0) {

                    // 分割字符串
                    String ss = s.substring(0, n);

                    if (!hash.contains(ss)) {

                        // 有一个不存在就出循环, 并使标志位 false
                        tmp = false;
                        break;
                    }

                    n--;
                }

                // 判断是否都存在
                if (tmp) {
                    max = s.length();
                    res = s;
                }
            }
        }

        // 返回结果
        return res;
    }
}